//
// Created by Zxy on 2020/8/16.
//

#ifndef QUICK_SORT_QUICKSORT_TWOWAYS_H
#define QUICK_SORT_QUICKSORT_TWOWAYS_H
#include <iostream>
#include <cassert>
#include <ctime>
using namespace std;

// 对arr[l...r]部分进行partition操作
// 返回p，使arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
template <typename T>
int partition2(T arr[], int l, int r){
    swap(arr[rand() % (r - l + 1) + l], arr[l]);
    T v = arr[l];
    // arr[l+1...i) <= v; arr(j...r] => v
    // 初始状态时两个区间都为空
    int i = l + 1, j = r;
    while(1){
        while(i <= r && arr[i] < v) i++;
        while(j >= l + 1 && arr[j] > v) j--;
        // 此时i指向第一个大于等于v的位置，j指向最后一个小于等于v的位置
        if(i > j) break;
        swap(arr[i], arr[j]);
        i++;
        j--;
    }
    swap(arr[l], arr[j]);
    return j;
}

// 对arr[l...r]部分进行快速排序
template <typename T>
void __quickSort2(T arr[], int l, int r){
    if(l >= r) return;
    int p = partition2(arr, l, r);
    __quickSort2(arr, l, p - 1);
    __quickSort2(arr, p + 1, r);
}

template <typename T>
void quickSort2(T arr[], int n){
    __quickSort2(arr, 0, n - 1);
}
#endif //QUICK_SORT_QUICKSORT_TWOWAYS_H
